package com.chb.mains;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description:
 * @author: CHB
 * @create: 2022-04-11 17:45
 **/
public class SolutionFourSum {

    public static void main(String[] args) {

        System.out.println(fourSum(new int[]{1,2,2,2,2,2}, 8));
        // double len = 7;
        // int ceil = (int) Math.ceil(len / 4);
        // String regex = String.format("(?<=\\w{%d})\\w*(\\w(?=\\w{%d}))", ceil, ceil);
        // String s = "F1234567".replaceAll(regex,"***");
        // System.out.println(regex+"   ---  "+s);
        // List<List<Integer>> res = new ArrayList<>();
        // res.add(Arrays.asList(2,2,2,2));
        // System.out.println(Arrays.asList(1, 1, 2, 2).hashCode());
        // System.out.println(Arrays.asList(1, 1, 2, 2).hashCode());
        // System.out.println(Arrays.asList(2, 1, 2, 2).hashCode());
        // boolean contains = res.contains(Arrays.asList(2, 2, 2, 2));
        // System.out.println(contains);
    }
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;

        for(int i = 0; i < len; i++){
            for(int j = len - 1; j > i+2; j--) {
                int sum = nums[i] + nums[j];
                int l = i + 1;
                int r = j - 1;
                while (l < r){
                    int lNum = nums[l];
                    int rNum = nums[r];
                    if (sum + lNum + rNum == target) {
                        if(!res.contains(Arrays.asList(nums[i],lNum,rNum,nums[j]))){
                            res.add(Arrays.asList(nums[i],lNum,rNum,nums[j]));
                        }
                        while (l < r && nums[l] == nums[l+1]){
                            l++;
                        }
                        while (l < r && nums[r] == nums[r+1]){
                            r--;
                        }
                        l++;
                        r--;
                    }else if(sum + lNum + rNum < target){
                        l++;
                    }else {
                        r--;
                    }
                }
            }
        }
        return res;
    }
}
